package problem;

import java.nio.file.Path;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class S_113 {
    //路径总和2
    /*给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。*/
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //回溯
    class Solution {
        private void findPath(TreeNode root,int sum,LinkedList<Integer> path,List<List<Integer>> res){
            if(root==null) return;
            path.add(root.val); //试探性添加
            if(root.left==null&&root.right==null&&root.val==sum){
                System.out.println(path);
                res.add(new LinkedList<>(path));
            }
            findPath(root.left,sum-root.val,path,res);
            findPath(root.right,sum-root.val,path,res);
            //path.remove(path.size()-1);
            path.removeLast();
        }
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            LinkedList<Integer> path=new LinkedList();
            List<List<Integer>> res=new ArrayList<>();
            findPath(root,sum,path,res);
            return res;
        }
    }


}
